package LeetcodeTest_thirty_four;
//分割链表
import java.util.List;
import java.util.Scanner;

public class partition
{
    public static void main(String[] args)
    {
        ListNode head=null;
        head=solution.createListNode();
        head=solution.partition(head,5);
        solution.Print(head);
    }
}
class solution {
    public static ListNode partition(ListNode head, int x)
    {
        ListNode root1=new ListNode(0);
        ListNode p1=root1;
        ListNode root2=new ListNode(0);
        ListNode p2=root2;
        ListNode p=head;
        while (p!=null)
        {
            if(p.val<x)
            {
               p1.next=p;
               p1=p;
               p=p.next;
               p1.next=null;
            }
            else
            {
                p2.next=p;
                p2=p;
                p=p.next;
                p2.next=null;
            }
        }
        p1.next=root2.next;
        return root1.next;
    }
    public static ListNode createListNode()
    {
        int a;
        Scanner reader=new Scanner(System.in);
        ListNode head=null;
        ListNode tail=null;
        head=new ListNode(0);
        tail=head;
        a=reader.nextInt();
        while(a!=-1)
        {
            ListNode p=new ListNode(a);
            tail.next=p;
            tail=tail.next;
            a=reader.nextInt();
        }
        return head.next;
    }
    public static void Print(ListNode head)
    {
        ListNode p=head;
        while(p!=null)
        {
            System.out.print(p.val+"   ");
            p=p.next;
        }
    }
}